package com.lw.leetcode.arr.b;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * arr
 * b
 * LCP 68. 美观的花束
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/8 17:42
 */
public class BeautifulBouquet {

    public static void main(String[] args) {
        BeautifulBouquet test = new BeautifulBouquet();

        // 8
//        int[] arr = {1,2,3,2};
//        int k = 1;

        // 8
//        int[] arr = {5, 3, 3, 3};
//        int k = 2;

        // 8
        int[] arr = Utils.getArr(100000, 1, 100000);
        int k = 10;
        System.out.println(k);

        int i = test.beautifulBouquet(arr, k);
        System.out.println(i);
    }


    public int beautifulBouquet(int[] flowers, int cnt) {
        int[] arr = new int[100001];
        int length = flowers.length;
        int index = -1;
        long sum = 0;
        for (int i = 0; i < length; i++) {
            int v = flowers[i];
            if (arr[v] == cnt) {
                index = find(flowers, arr, v, index);
            } else {
                arr[v]++;
            }
            sum = (sum + i - index) % 1000000007;
        }
        return (int) sum;
    }

    private int find(int[] flowers, int[] arr, int v, int index) {
        index++;
        while (flowers[index] != v) {
            arr[flowers[index]]--;
            index++;
        }
        return index;
    }

}
